package 回溯.不熟;

/**
 * todo
 *
 * @author songZiHao
 * @version 1.0.0
 * @ClassName 两个回文子序列长度的最大乘积2002.java
 * @createTime 2023年07月31日 15:45:00
 */
public class 两个回文子序列长度的最大乘积2002 {

	private int maxProduct;

	public int maxProduct(String s) {
		maxProduct = 0;
		backtrack(s, 0, "", "");
		return maxProduct;
	}

	private void backtrack(String s, int index, String s1, String s2) {
		if (index == s.length()) {
			if (!s1.isEmpty() && !s2.isEmpty() && isPalindrome(s1) && isPalindrome(s2)) {
				int product = s1.length() * s2.length();
				maxProduct = Math.max(maxProduct, product);
			}
			return;
		}

		char c = s.charAt(index);
		//跳过这个字符
		backtrack(s, index + 1, s1, s2);
		//字符算在左边
		backtrack(s, index + 1, s1 + c, s2);
		//字符算在右边
		backtrack(s, index + 1, s1, s2 + c);
	}

	private boolean isPalindrome(String s) {
		int left = 0;
		int right = s.length() - 1;
		while (left < right) {
			if (s.charAt(left) != s.charAt(right)) {
				return false;
			}
			left++;
			right--;
		}
		return true;
	}

}
